package bintree.leetcode;

/**
 * @author yuisama
 * @date 2023年07月11日 13:26
 * @description 树的子结构
 */
public class Offer26_SubStructure {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        // A的子树存在B的结构或A包含B
        return isSubStructure(A.left,B) || isSubStructure(A.right,B) || isContains(A,B);
    }
    // 输入两颗树t1，t2，判断以t1为根的树是否包含t2
    private boolean isContains(TreeNode t1, TreeNode t2) {
        if (t2 == null) {
            return true;
        }
        if (t1 == null || t1.val != t2.val) {
            // 当前两颗树根节点不同，以t1为根的树不包含t2
            return false;
        }
        // 左树和右树也包含
        return isContains(t1.left,t2.left) && isContains(t1.right,t2.right);
    }
}
